/*
	解法：双指针 或 递归
	为什么：双指针+一个临时变量保存当前节点的下一个节点
	时间复杂度：O(n)（遍历一次链表），空间复杂度：O(1)（只用了常数级的指针变量）
 */

#include <iostream>
#include <vector>

using namespace std;

// 链表节点定义（含三个构造函数）
struct ListNode
{
	int val;
	ListNode* next;
	
	ListNode() : val(0), next(nullptr) {}
	ListNode(int x) : val(x), next(nullptr) {}
	ListNode(int x, ListNode* next) : val(x), next(next) {}
};

class Solution
{
public:
	ListNode* reverseList(ListNode* head)
	{
		ListNode* prev = nullptr;
		ListNode* curr = head;
		
		while (curr != nullptr)
		{
			ListNode* nextTemp = curr->next;
			curr->next = prev;
			prev = curr;		//先移动pre
			curr = nextTemp;	//后移动curr
		}
		
		return prev;
	}
};

// 构建链表的辅助函数
ListNode* buildList(const vector<int>& nums)
{
	ListNode* dummy = new ListNode(-1);
	ListNode* tail = dummy;
	
	for (size_t i = 0; i < nums.size(); ++i)
	{
		tail->next = new ListNode(nums[i]);
		tail = tail->next;
	}
	
	ListNode* head = dummy->next;
	delete dummy;
	return head;
}

// 打印链表的辅助函数
void printList(ListNode* head)
{
	while (head != nullptr)
	{
		cout << head->val;
		if (head->next != nullptr)
		{
			cout << " -> ";
		}
		head = head->next;
	}
	cout << endl;
}

// 释放链表内存的辅助函数
void deleteList(ListNode* head)
{
	while (head != nullptr)
	{
		ListNode* temp = head;
		head = head->next;
		delete temp;
	}
}

int main()
{
	// 示例输入：{1, 2, 3, 4, 5}
	vector<int> nums = {1, 2, 3, 4, 5};
	ListNode* head = buildList(nums);
	
	cout << "原始链表: ";
	printList(head);
	
	Solution sol;
	ListNode* reversed = sol.reverseList(head);
	
	cout << "反转后链表: ";
	printList(reversed);
	
	deleteList(reversed);
	
	return 0;
}


